#include <stdio.h>
#include <stdlib.h>
#include <limits.h>

typedef int bool;
#define true 1
#define false 0

struct EdgeNode
{
    int dest;
    int weight;
    struct EdgeNode* next;
};


struct Edge
{
    struct EdgeNode *head; 
};

struct Graph
{
    int V;
    struct Edge* array;
};

struct EdgeNode* newEdgeNode(int dest, int weight)
{
    struct EdgeNode* newNode =
            (struct EdgeNode*) malloc(sizeof(struct EdgeNode));
    newNode->dest = dest;
    newNode->weight = weight;
    newNode->next = NULL;
    return newNode;
}


struct Graph* createGraph(int V)
{
    struct Graph* graph = (struct Graph*) malloc(sizeof(struct Graph));
    graph->V = V;


    graph->array = (struct Edge*) malloc(V * sizeof(struct Edge));
    int i;

    for (i = 0; i < V; ++i)
        graph->array[i].head = NULL;

    return graph;
}


void addEdge(struct Graph* graph, int src, int dest, int weight)
{


    struct EdgeNode* newNode = newEdgeNode(dest, weight);
    newNode->next = graph->array[src].head;
    graph->array[src].head = newNode;


    newNode = newEdgeNode(src, weight);
    newNode->next = graph->array[dest].head;
    graph->array[dest].head = newNode;
}


struct HeapNode
{
    int  v;
    int key;
};


struct Heap
{
    int size;     
    int capacity; 
    int *pos;  
    struct HeapNode **array;
};


struct HeapNode* newMinHeapNode(int v, int key)
{
    struct HeapNode* minHeapNode =
           (struct HeapNode*) malloc(sizeof(struct HeapNode));
    minHeapNode->v = v;
    minHeapNode->key = key;
    return minHeapNode;
}


struct Heap* createMinHeap(int capacity)
{
    struct Heap* minHeap =
         (struct Heap*) malloc(sizeof(struct Heap));
    minHeap->pos = (int *)malloc(capacity * sizeof(int));
    minHeap->size = 0;
    minHeap->capacity = capacity;
    minHeap->array =
         (struct HeapNode**) malloc(capacity * sizeof(struct HeapNode*));
    return minHeap;
}


void swap(struct HeapNode** a, struct HeapNode** b)
{
    struct HeapNode* t = *a;
    *a = *b;
    *b = t;
}

void heapify(struct Heap* heap, int idx)
{
    int smallest, left, right;
    smallest = idx;
    left = 2 * idx + 1;
    right = 2 * idx + 2;

    if (left < heap->size &&
        heap->array[left]->key < heap->array[smallest]->key )
      smallest = left;

    if (right < heap->size &&
        heap->array[right]->key < heap->array[smallest]->key )
      smallest = right;

    if (smallest != idx)
    {
        struct HeapNode *smallestNode = heap->array[smallest];
        struct HeapNode *idxNode = heap->array[idx];

        heap->pos[smallestNode->v] = idx;
        heap->pos[idxNode->v] = smallest;

        swap(&heap->array[smallest], &heap->array[idx]);

        heapify(heap, smallest);
    }
}

struct HeapNode* findMin(struct Heap* heap)
{
    if (heap==0)
        return NULL;


    struct HeapNode* root = heap->array[0];


    struct HeapNode* lastNode = heap->array[heap->size - 1];
    heap->array[0] = lastNode;


    heap->pos[root->v] = heap->size-1;
    heap->pos[lastNode->v] = 0;


    --heap->size;
    heapify(heap, 0);

    return root;
}

void updateKey(struct Heap* heap, int v, int key)
{

    int i = heap->pos[v];


    heap->array[i]->key = key;

    while (i && heap->array[i]->key < heap->array[(i - 1) / 2]->key)
    {
        heap->pos[heap->array[i]->v] = (i-1)/2;
        heap->pos[heap->array[(i-1)/2]->v] = i;
        swap(&heap->array[i],  &heap->array[(i - 1) / 2]);
        i = (i - 1) / 2;
    }
}

bool isInHeap(struct Heap *heap, int v)
{
   if (heap->pos[v] < heap->size)
     return true;
   return false;
}

void Prim(struct Graph* graph)
{
    int V = graph->V;
    int parent[V]; 
    int key[V];     


    struct Heap* heap = createMinHeap(V);

    int v, totallyWeight=0;
    for (v = 1; v < V+1; ++v){
        parent[v] = -1;
        key[v] = INT_MAX;
        heap->array[v] = newMinHeapNode(v, key[v]);
        heap->pos[v] = v;
    }

    key[0] = 0;
    heap->array[0] = newMinHeapNode(0, key[0]);
    heap->pos[0]   = 0;

    heap->size = V;



    while(heap->size != 0)
    {

        struct HeapNode* heapNode = findMin(heap);
        int u = heapNode->v; 

        totallyWeight = totallyWeight + heapNode->key;

        struct EdgeNode* pCrawl = graph->array[u].head;
        while (pCrawl != NULL)
        {

            int v = pCrawl->dest;

            if (isInHeap(heap, v) && pCrawl->weight < key[v])
            {
                key[v] = pCrawl->weight;
                parent[v] = u;
                updateKey(heap, v, key[v]);
            }
            pCrawl = pCrawl->next;
        }
    }

    int i;
    for (i = 1; i < V; ++i)
        printf("%d - %d\n", parent[i]+1, i+1);

    printf("totallyWeight: %d \n", totallyWeight);
}


int main()
{
    int V,E,heapSize=0,startVertices,endVertices,weight, totallyWeight=0 ;
    int x, i=0,j, temp=0 , now;

    FILE *myFile;
    FILE *fp;
    fpos_t dlugosc, MAXdlugosc;

    if ((myFile=fopen("c:\\1.in", "rb"))==NULL || (fp=fopen("c:\\1.in", "rb"))==NULL ) {
    printf ("B³¹d otwarcia pliku: %s!\n", "c:\\tekst.txt");
    return 1;
    }
    fseek (fp, 0, SEEK_END); /* ustawiamy wskaŸnik na koniec pliku */
    fgetpos (fp, &dlugosc);
    MAXdlugosc=dlugosc+1;

    //read file into array
    int firstArray[2]; // array of numbers of edges and vertices

    if (myFile == NULL){
        printf("Error Reading File\n");
        exit (0);
    }
    for (i = 0; i <= 1 ; i++){
        fscanf(myFile, "%d", &firstArray[i] );
    }

    V = firstArray[0];
    E = firstArray[1];
    int numberArray[E*3 + 1];


    for (i = 1 ; i < firstArray[1]*3+1; i++){
            fscanf(myFile, "%d", &numberArray[i] );
    }

    fclose(myFile);

    struct Graph* graph = createGraph(V);
    for (i = 1; i < E*3-1;){

        printf("i: %d \n",i);
        temp=i;
        startVertices =numberArray[i]-1;
        endVertices =numberArray[i+1]-1;
        weight = numberArray[i+2];

        addEdge(graph, startVertices, endVertices, weight);

        i=temp+3;

    }
/* ----------------------------------------------------------*/
    Prim(graph);

    return 0;
}
